Numerous implementations of the conventional division algorithm known as higher radix nonrestoring division ("SRT division") have been proposed. SRT division is an iterative algorithm in which one or more quotient bits are generated during each iteration, and in which positive and negative quotient bit component signals are resolved into a final quotient vector signal at the end of the last iteration.
In SRT division, the quotient bit representations are redundant in the sense that any one quotient bit may be represented in several different ways by different combinations of positive and negative quotient bit component signals. At the end of the last iteration during SRT division, it is conventional to convert the quotient bit representation (containing positive and negative component signals) to an irredundant representation (containing no negative component signals) by subtracting the negative quotient bit components from the positive quotient bit components.
In radix 2.sup.n SRT division, n quotient bits are generated per iteration. Radix 2.sup.n SRT division is the most convenient form of SRT division for binary hardware implementation, since it allows the final quotient to be conveniently formed by concatenating the individual quotient bits. For example, a preferred embodiment of the inventive divider circuit performs radix 4 SRT division.
Because of the redundancy in the quotient digit representations in SRT division, it is not necessary to calculate quotient bits exactly. Instead, SRT division circuits generate predictions of each quotient bit based upon approximations of the operands. Such approximations are obtained by examining only the few most significant bits of the divisor and partial remainder during each iteration. Any errors in prediction of quotient bits are corrected during later iterations by less significant quotient bits of the opposite sign.
Conventional SRT division circuits have employed quotient bit prediction units with large look-up tables (implemented as complicated programmable logic arrays). It would be highly desirable to minimize table storage requirements in SRT division circuits, and thus to reduce the number of transistors and other circuit elements required for implementing the quotient bit prediction look-up tables. However, until the present invention, it was not known how to accomplish this objective.